% Version control information:
%\svnid{$Id: programacion_dinamica.tex 7 2009-04-20 22:10:35Z asalber $
%
\subsection{Programación dinámica}
%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Técnica de programación dinámica}
Con la técnica de divide y vencerás, la descomposición natural de un problema puede originar subproblemas que se solapen, de manera que al resolverlos independientemente se acabe resolviendo el mismo problema múltiples veces.

La técnica de \textbf{programación dinámica} es similar a la de divide y vencerás, sólo que los subproblemas obtenidos sólo se resuelven una vez. 

Esto exige guardar la solución de cada subproblema para, si se presenta de nuevo, no tener que volver a resolverlo.

\centerline{\emph{¡Se sacrifica espacio para ganar tiempo de ejecución!}}

Es una técnica ascendente, que se inicia con la resolución de subproblemas más pequeños, y utiliza sus soluciones en la resolución de los subproblemas de niveles superiores.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Los números de Fibonacci}
La sucesión de Fibonacci viene dada por la expresión:
\[
f(n)=
\begin{cases}
1 & \mbox{si $n<2$}\\
f(n-1)+f(n-2) & \mbox{si $n\geq 2$}
\end{cases}
\]
El algoritmo resultante utilizando divide y vencerás es
\begin{lstlisting}
long int fibonacci(int n){
  if (n<2) return 1;
  else return fibonacci(n-2)+fibonacci(n-1);
}
\end{lstlisting}
\alert{\emph{En la resolución se repiten llamadas recursivas}}
\begin{center}

\pstree[nodesep=2pt,levelsep=1cm]{\TR{$f(n)$}}{ 
  \pstree{\TR{$f(n-1)$}}{
       \pstree{\TR{$f(n-2)$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
       \pstree{\TR{\alert{$f(n-3)$}}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
  } 
  \pstree{\TR{$f(n-2)$}}{
       \pstree{\TR{\alert{$f(n-3)$}}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
       \pstree{\TR{$f(n-4)$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
  }
}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Los números de Fibonacci}
Resulta sencillo evitar la repetición de llamadas recursivas utilizando el siguiente esquema:

\bigskip
\begin{center}
\psset{arrows=<-,linestyle=dashed}
\pstree[treemode=R,nodesep=2pt]{\TR[name=n]{$f(n$)} }{
	\pstree{ \TR[name=n-1]{$f(n-1)$} }{
		\pstree{ \TR[name=n-2]{$f(n-2)$} }{
			\pstree{ \TR[name=n-3]{$f(n-3)$} }{ \TR{$\cdots$} }
		}
	}
}
\nccurve[linestyle=dashed,angleA=150,ncurvA=1,angleB=30,ncurB=1]{->}{n-2}{n}
\nccurve[linestyle=dashed,angleA=150,ncurvA=1,angleB=30,ncurB=1]{->}{n-3}{n-1}
\end{center}

La siguiente función en C++ calcula la sucesión de Fibonacci hasta el térnimo $n$ con programación dinamica:
\begin{lstlisting}
// fibonacci.cpp
int * fibonacci(int f[n]){ // Se supone n>2
  f[0]=0;
  f[1]=1;
  for(int i=2; i<=n; i++)
    f[i]=f[i-1]+f[i-2];
  return f;
}
\end{lstlisting}
El coste de este algoritmo es $O(n)$ frente a $O(2^n)$ del anterior.
\end{frame}


\begin{frame}
\frametitle{Características de la programación dinámica}
Para que un problema pueda resolverse por la técnica de programación dinámica debe cumplir el siguiente principio:

\begin{block}{Principio de optimalidad}
En una secuencia óptima de decisiones, toda subsecuencia también ha de ser óptima.
\end{block}

La descomposición en subproblemas suele hacerse de acuerdo a este principio.

La estructura de datos donde se van guardando las soluciones de los subproblemas resueltos suele ser una tabla.

La mayor dificultad de esta técnica consiste en determinar el orden en que se deberá rellenar la tabla. Para resolver un subproblema, previamente deben estar almacenadas todas las soluciones necesarias.

La programación dinámica supone un compromiso entre el coste espacial y el coste temporal. Si para reducir un poco el coste temporal se requiere un excesivo coste espacial, puede no ser una buena técnica.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplos de algoritmos con programación dinámica}
Algunos problemas conocidos que pueden resolverse mediante la técnica de programación dinámica son:
\begin{itemize}
\item El cálculo de los números de Fibonacci.
\item El cálculo de números combinatorios.
\item El problema de la mochila entera.
\item El problema de los caminos mínimos en grafos.
\item La multiplicación de una secuencia de matrices.
\item El problema del viajante.
\end{itemize}
\end{frame}


\subsubsection{El problema del cambio de monedas}
%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del cambio de monedas}
\framesubtitle{Ejemplo de programación dinámica}
Dado un conjunto $M$ de monedas de $n$ tipos con valores $m_1,\ldots,m_n$, se
trata de encontrar el número mínimo de monedas que sumen una cantidad $x$.
\[
\includegraphics[scale=0.8]{img/monedas.eps} 
\]
Ya vimos que la técnica voraz sólo permitía resolver el problema para
determinados tipos de sistemas monetarios. 

Ahora veremos una forma de resolver el problema mediante programación dinámica,
válida para cualquier sistema monetario.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del cambio de monedas}
\framesubtitle{Principio de optimalidad y función de recurrencia}
El problema del cambio de coneda satisface el principio de optimalidad, lo que
quiere decir que si $S=\{m_1,\ldots,m_{k-1},m_k\}$ es solución al problema de
devolver la cantidad $x$, y por tanto, $k$ es el mínimo número de monedas tal
que $\sum_{i=1}^k m_i =x$, entonces $S'=\{m_1,\ldots,m_{k-1}\}$ debe ser
solución óptima al problema de devolver la cantidad $x-m_k$.

Esto permite construir una función para el cambio de manera recursiva.
Dicha función dependerá del la cantidad a devolver y del número de tipos de moneda
disponibles. Así pues, definimos $C(i,j)$ con el número mínimo de monedas
necesarias para devolver la cantidad $j$ con los $i$ primeros tipos de moneda.
Dicha función puede expresarse recursivamente mediante la ecuación
\[
C(i,j) = 
\begin{cases}
0 & \mbox{si $j=0$},\\
\infty & \mbox{si $j>0, i=0$},\\
C(i-1,j) & \mbox{si $j>0,i>0,m_i>j$},\\
\min\{C(i-1,j),C(i,j-m_i)+1\} & \mbox{si $j>0,i>0,m_i\leq j$}.
\end{cases}
\]
Esta función se conoce como $\textbf{función de recurrencia}$ del problema. 
%Los dos primeros casos son los casos base que finalizan la recursión. El
%tercer caso se da cuando el valor de la moneda de tipo $i$ es mayor que la
%cantidad a devolver, en cuyo caso no podrá tomarse ninguna moneda de ese tipo
%y la solución se calculará recursivamente para los $i-1$ tipos de moneda
%restantes. Y el último caso se da cuando el valor de la moneda de tipo $i$ es
%menor o igual a la cantidad a devolver, con lo cual existen dos posibilidades,
%tomar una moneda de tipo $i$ en el cambio o no tomarla, y hay que devolver el
%mínimo de ambas. 
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del cambio de monedas}
\framesubtitle{Tabla dinámica}
Al igual que ocurría en el problema de la mochila es espacio de búsqueda del
problema es exponencial, sin embargo el número de posibles llamadas a la
función $C(i,j)$, para $n$ tipos de monedas y una cantidad $x$ a devolver es
$(n+1)(x+1)$, de manera que, necesariamente en el espacio de búsqueda se
repiten llamadas y para evitar repetir cálculos conviene ir guardando las
soluciones en una tabla dinámica. 

Como la función $C(i,j)$ depende de dos parámetros, utilizaremos una tabla
bidimensional donde el número de monedas disonible $i$ será la fila y la
cantidad a devolver $j$ será la columna. 

\[
\begin{array}{|c|c|c|c|c|c}
\multicolumn{1}{c}{} & \multicolumn{4}{c}{\mbox{Cantidad a devolver}} & \\
\cline{2-5}
\multicolumn{1}{c|}{\mbox{nº monedas}} & 0 & 1 & \cdots & x & \\
\cline{1-5}
1 & c(1,0) & c(1,1) & \cdots & c(1,x) & \\
\cline{1-5}
2 & c(2,0) & c(2,1) & \cdots & c(2,x) & \\
\cline{1-5}
\vdots & \vdots & \vdots & \ddots & \vdots & \\
\cline{1-5}
n & c(n,0) & c(n ,1) & \cdots & \mbox{\alert{$c(n,x)$}} & \leftarrow
\mbox{SOLUCIÓN} \\
\cline{1-5}
\end{array}
\]
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del cambio de monedas}
\framesubtitle{Cómo rellenar la tabla dinámica}
Cuando para resolver el problema original es necesario rellenar la mayor parte
de la tabla, es más eficiente hacerlo de manera iterativa. Para ello es
importante saber en qué orden debe hacerse.

Si nos fijamos en la construcción recursiva de la función $C(i,j)$, veremos que
para poder calcular el valor de la celda de la fila $i$ y la columna $j$
necesitaremos tener ya calculadas las celdas de la fila $i-1$ y columna $j$ y
la de la fila $i$ y columna $j-m_i$. La columna de esta última celda dependerá
del valor $m_i$ de la moneda de tipo $i$, pero, en cualquier caso, será una
columna anterior a $j$.

\begin{center}
\scalebox{0.8}{
\begin{pspicture}(0,0)(7,2)
\rput[b](3,0){
\[
\renewcommand{\arraystretch}{2}
\begin{array}{c|c|c|c|c|c|}
\multicolumn{2}{c}{} & \multicolumn{1}{c}{j-m_i} & \multicolumn{1}{c}{} &
\multicolumn{1}{c}{j} & \multicolumn{1}{c}{} \\
 \cline{2-6}
 i-1 & \cdots & \cdots & \cdots & \cellcolor{orange}C(i-1,j) & \cdots\\
 \cline{2-6}
 i & \cdots & \cellcolor{orange} C(i,j-m_i) & \cdots & \cellcolor{green} C(i,j)
 & \cdots\\
 \cline{2-6}
\end{array}
\]
}
\psset{linewidth=1.5pt}
\psline{->}(3.2,0.35)(4.6,0.35)
\psline{->}(5.2,1)(5.2,0.5)
\end{pspicture}
}
\end{center}
Esto permite rellenar la tabla iterativamente, de arriba a abajo y de izquierda
a derecha. 
\end{frame} 


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema del cambio de monedas}
\framesubtitle{Implementación en Java (versión iterativa)}
\begin{lstlisting}
/* cambio.java
 * v[] es un vector con los valores de las monedas.
 * x es la cantidad a devolver.
 * Devuelve el minimo numero de monedas que suman la cantidad x.
 */
public int cambio(int v[], int x){
	int t[][] = new int[v.length+1][x+1];  // Tabla dinamica
	// Rellenamos los casos base de la tabla
	for (int i=0; i<=v.length; i++) t[i][0] = 0;
	for (int j=1; j<=x; j++) t[0][j] = INF;
	// Rellenamos el resto de la tabla
	for (int i=1; i<=v.length; i++){
		for (int j=1; j<=x; j++)
            if (v[i-1]>j) t[i][j] = t[i-1][j];
			else t[i][j] = Math.min(t[i-1][j], t[i][j-v[i-1]]+1);
	}
	return t[v.length][x];
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del cambio de monedas}
\framesubtitle{Coste temporal y espacial}
El coste temporal del algoritmo anterior depende del doble bucle que rellena la
tabla, y puesto que el cálculo de cada celda requiere un tiempo constante, será
del orden de las dimensiones de la tabla, es decir, $(n+1)(x+1)$. Como
normalmente la cantidad a devolver $x$ será mayor que el número de tipos de
monedas $n$, podemos acotarlo superiormente por un orden cuadrático en $O(x^2)$.

El coste espacial es la memoria que requiere la tabla dinámica, que tiene
$(n+1)(x+1)$ celdas y por tanto, también sería cuadrático, por lo que,
\emph{\alert{cuando la cantidad a devolver $x$ sea demasiado grande, este
algoritmo sería impracticable}}. 
\end{frame} 


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del cambio de monedas}
\framesubtitle{Reducción del coste espacial}
Afortunadamente, es posible reducir el coste espacial a un orden lineal. 

Si nos fijamos en el orden de construcción de la tabla dinámica, realmente sólo
se requiere un vector fila de la tabla, que puede ir reescribiéndose para cada
valor de $i$. Lo único que hay que garantizar es que no se reescribe ninguna
celda cuyo contenido se necesite después. Pero en el cálculo de la celda
$C(i,j)$ sólo se necesita el valor $C(i-1,j)$ de la fila anterior, que al
utilizar el mismo vector para la fila $i-1$ y para la $i$, realmente se
corresponde con la misma posición $j$ del vector.

\begin{center}
\scalebox{0.8}{
\begin{pspicture}(0,0)(7,3)
\rput[b](3,1.5){
\[
\renewcommand{\arraystretch}{2}
\begin{array}{|c|c|c|c|c|}
\multicolumn{1}{c}{} & \multicolumn{1}{c}{j-m_i} & \multicolumn{1}{c}{} &
\multicolumn{1}{c}{j} & \multicolumn{1}{c}{} \\
\hline
 \cdots & \cellcolor{orange}C(i,j-m_i) & \cdots &
 \uncover<1-2>{\cellcolor{orange}}\uncover<3->{\cellcolor{green}}
 \qquad\qquad\qquad & \cdots\\
\hline
\end{array}
\]
}
\uncover<1-2>{\rput[b](4.6,1.65){$C(i-1,j)$}}
\uncover<2>{
\rput[b](2.2,0){$C(i,j)=\min\{C(i,j-m_i)+1,C(i-1,j)\}$}
\psline{->}(4.6,1.5)(4.6,0.5)
\psline{->}(1.8,1.5)(1.8,0.5)
} 
\uncover<2->{
\rput[b](2.2,0){$C(i,j)=\min\{C(i,j-m_i)+1,C(i-1,j)\}$}
} 
\uncover<3>{
\rput[b](4.6,1.65){$C(i,j)$}
\pscurve{->}(0,0.5)(0.8,1.1)(4.3,0.9)(4.6,1.5)} 
\end{pspicture}
}
\end{center}
\end{frame} 


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema del cambio de monedas}
\framesubtitle{Implementación en Java (versión iterativa con ahorro
de memoria)}
\begin{lstlisting}
/* cambio.java
 * v[] es un vector con los valores de las monedas.
 * x es la cantidad a devolver.
 * Devuelve el minimo numero de monedas que suman la cantidad x.
 */
public int cambio(int v[], int x){
	int t[] = new int[x+1];  // Vector dinamico
	// Rellenamos los casos base
	t[0] = 0;
	for (int i=1; i<=x; i++) t[i] = INF;
	// Rellenamos el resto de la tabla sobre el mismo vector.
	for (int i=0; i<v.length; i++){
		for (int j=v[i]; j<=x; j++)
			t[j] = Math.min(t[j], t[j-v[i]]+1);
	}
	return t[x];
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del cambio de monedas}
\framesubtitle{Cálculo del cambio mínimo}
Si queremos obtener el cambio mínimo, podemos hacerlo a partir del vector
dinámico partiendo de la última celda, la que contiene el
número mínimo de monedas, y recorriéndolo hacia atrás al tiempo que
consideramos los distintos tipos de monedas, del último al primero, de acuerdo a lo siguiente:
\begin{itemize}
  \item Si estamos en la celda $j$ y $m_i>j$, entonces podemos descartar las
  monedas del tipo $i$ ya que no pueden utilizarse para devolver la cantidad
  $j$.
  \item Si estamos en la celda $j$ y $m_i<=j$, entonces hay que ver de dónde
  proviene el valor de dicha celda. Recordemos que en tal caso 
  \[
  \item C(i,j)=\min\{C(i-1,j),C(i,j-m_i)+1\}
  \]
  El valor de $C(i-1,j)$ ya no está disponible en el vector pues se perdió a
  escribir la fila $i$, pero si disponemos del valor $C(i,j-m_i)$ que estará
  precisamente en la posición $j-m_i$ del vector. Por tanto la decisión de
  tomar o no una moneda más del tipo $i$ depende de 
  \[
  \begin{cases}
  \mbox{Si $t[j] = t[j-m_i]+1 \rightarrow$ Tomar una moneda más del tipo $i$,}\\
  \mbox{Si $t[i]\neq t[j-m_i]+1 \rightarrow$ No tomar más monedas del tipo $i$.}
  \end{cases}
  \]
\end{itemize}
\end{frame} 


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema del cambio de monedas}
\framesubtitle{Implementación en Java del cálculo del cambio mínimo}
\begin{lstlisting}
/* cambio.java
 * v[] es un vector con los valores de las monedas.
 * t[] es el vector dinamico del algoritmo anterior.
 * x es la cantidad a devolver.
 * Devuelve el numero de monedas de cada tipo en el cambio.
 */
public int[] obtenerCambio(int v[], int t[], int x){
  int cambio[] = new int[v.length];
  if (t[x] != INF) {// Si no es que no hay solucion al problema.
    int i = v.length-1;
    while (x>0)
      if (v[i]<=x && t[x]==t[x-v[i]]+1){
        // Tomamos otra moneda del tipo i
        cambio[i]++;
        x -= v[i];
      }
      else // Ya no se toman mas monedas del tipo i
        i--;
    }
    return cambio;
}
\end{lstlisting}
\end{frame}


\subsubsection{El problema de la mochila entera}
%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema de la mochila entera}
\framesubtitle{Ejemplo de programación dinámica}
Ya vimos un algoritmo voraz para resolver el problema de la mochila fraccionaria, sin embargo, la técnica voraz no garantiza la obtención de la solución óptima cuando los objetos no se pueden fraccionar. 

\textbf{Ejemplo}. Si tenemos una mochila con peso máximo 10 y los siguientes 3 objetos
\[
\begin{array}{|l|c|c|}
\cline{2-3}
\multicolumn{1}{c|}{} & \mbox{Valor} & \mbox{Peso}\\
\hline
\mbox{Objeto 1} & 18 & 6 \\
\hline
\mbox{Objeto 2} & 20 & 4 \\
\hline
\mbox{Objeto 3} & 12 & 2 \\
\hline
\end{array}
\] 
entonces el algoritmo voraz decide introducir en la mochila el objeto 2 y 3 acumulando un valor 32, mientras que la solución óptima es meter los objetos 1 y 2 que suman un valor 38.

Veremos cómo la programación dinámica si permite llegar a la solución óptima.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema de la mochila entera}
\framesubtitle{Función de recurrencia}
Supongamos que tenemos una mochila de capacidad $p_{max}$ y disponemos de $n$
objetos para llenarla.

El valor máximo de la mochila dependerá de la capacidad y del número de
objetos disponibles. Si llamamos $f(i,j)$ al valor máximo que se puede
conseguir cuando en la mochila queda una capacidad $j$ y disponemos de $i$ objetos para llenarla, está claro que la solución al problema de la mochila entera será $f(n,p_{max})$.

Aplicando el principio de optimalidad, podemos definir esta función de
recurrencia mediane la siguiente ecuación:
\[
f(i,j)=
\begin{cases}
0 & \mbox{si $i=1$ y $j<p_1$}\\
v_1 & \mbox{si $i=1$ y $j\geq p_1$}\\
f(i-1,j) & \mbox{si $i>1$ y  $j<p_i$}\\
\max\{f(i-1,j),f(i-1,j-p_i)+v_i\} & \mbox{si $i>1$ y $j\geq p_i$}
\end{cases}
\]
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema de la mochila entera}
\framesubtitle{Tabla dinámica}
El algoritmo recursivo que implementa directamente la función anterior tiene un coste exponencial $O(2^n)$.

Sin embargo, el número total de subproblemas a resolver no es tan grande, ya que el primer parámetro de $f$ puede oscilar entre 1 y $n$, y el segundo entre 0 y $p_{max}$, en total $n(p_{max}+1)$.

Así pues, \alert{\emph{¡hay subproblemas que se repiten!}}

Para evitar resolver cada subproblema más de una vez, podemos utilizar una tabla para almacenar los subproblemas resueltos, en la que en la posición $(i,j)$ se almacene el valor de $f(i,j)$.
\[
\begin{array}{|c|c|c|c|c|c}
\multicolumn{1}{c}{} & \multicolumn{4}{c}{\mbox{peso disponible en la mochila}} & \\
\cline{2-5}
\multicolumn{1}{c|}{\mbox{nº objetos}} & 0 & 1 & \cdots & p_{max} & \\
\cline{1-5}
1 & f(1,0) & f(1,1) & \cdots & f(1,p_{max}) & \\
\cline{1-5}
2 & f(2,0) & f(2,1) & \cdots & f(2,p_{max}) & \\
\cline{1-5}
\vdots & \vdots & \vdots & \ddots & \vdots & \\
\cline{1-5}
n & f(n,0) & f(n ,1) & \cdots & \mbox{\alert{$f(n,p_{max})$}} & \leftarrow \mbox{SOLUCIÓN} \\
\cline{1-5}
\end{array}
\]
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema de la mochila entera}
\framesubtitle{Implementación en C++ (versión recursiva)}
\begin{lstlisting}
/* mochila_entera.cpp
 * v valores de los objetos
 * p pesos de los objetos
 * i numero de objetos
 * j capacidad de la mochila
 * f es la tabla dinamica 
 */
int mochila(int *v, int *p, int i, int j, int **f){
  if (f[i][j]>=0) return f[i][j];
  if (i==0 && p[0]>j) f[0][j] = 0; 
  else if (i==0 && p[0]<=j) f[0][j] = v[0];
  else if (j<p[i]) f[i][j] = mochila(v,p,i-1,j,f);
  else f[i][j] = 
    max(mochila(v,p,i-1,j,f), mochila(v,p,i-1,j-p[i],f)+v[i]);
  return f[i][j];
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del cambio de monedas}
\framesubtitle{Cómo rellenar la tabla dinámica}
Para rellenar la tabla dinámica iterativamente necesitamos saber en qué orden
debe rellenarse.

Si nos fijamos en la construcción recursiva de la función $f(i,j)$, veremos que
para poder calcular el valor de la celda de la fila $i$ y la columna $j$
necesitaremos tener ya calculadas las celdas de la fila $i-1$ y columna $j$ y
la de la fila $i-1$ y columna $j-p_i$. La columna de esta última celda dependerá
del peso $p_i$ del objeto $i$, pero, en cualquier caso, será una
columna anterior a $j$.

\begin{center}
\scalebox{0.8}{
\begin{pspicture}(0,0)(7,2)
\rput[b](3,0){
\[
\renewcommand{\arraystretch}{2}
\begin{array}{c|c|c|c|c|c|}
\multicolumn{2}{c}{} & \multicolumn{1}{c}{j-p_i} & \multicolumn{1}{c}{} &
\multicolumn{1}{c}{j} & \multicolumn{1}{c}{} \\
 \cline{2-6}
 i-1 & \cdots & f(i-1,j-p_i) & \cdots & f(i-1,j) & \cdots\\
 \cline{2-6}
 i & \cdots & \cdots & \cdots & f(i,j) & \cdots\\
 \cline{2-6}
\end{array}
\]
}
\psline{->}(3.2,1)(4.6,0.35)
\psline{->}(5.2,1)(5.2,0.5)
\end{pspicture}
}
\end{center}
Así pues, podemos rellenar la tabla de arriba a abajo.
\end{frame} 


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema de la mochila entera}
\framesubtitle{Implementación en C++ (versión iterativa)}
\begin{lstlisting}
/* mochila_entera.cpp
 * n numero de objetos
 * v[n] valores de los objetos
 * p[n] pesos de los objetos
 * pmax capacidad de la mochila
 */
void tabla_f(int n,int v[n],int p[n],int pmax,int f[n][pmax]){
  for (int j=0;j<=pmax;j++)
    if (j<p[0]) f[0][j]=0;
    else f[0][j]=v[0];
  for (int i=1; i<n; i++)
    for (int j=0;j<=pmax;j++)
      if (j<p[i]) f[i][j]=f[i-1][j];
      else 
        if (f[i-1][j]>f[i-1][j-p[i]]+v[i])
          f[i][j] = f[i-1][j];
        else f[i][j] = f[i-1][j-p[i]]+v[i];
  return;
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema de la mochila entera}
\framesubtitle{Ejemplo con programación dinámica}
Supongamos que tenemos una mochica de capaciada $p_{max}=10$ y disponemos de 5
objetos con los siguientes pesos y valores 
\[
\begin{array}{|l|c|c|}
\cline{2-3}
\multicolumn{1}{c|}{} & \mbox{Valor} & \mbox{Peso}\\
\hline
\mbox{Objeto 0} & 20 & 5 \\
\hline
\mbox{Objeto 1} & 15 & 4 \\
\hline
\mbox{Objeto 2} & 10 & 2 \\
\hline
\mbox{Objeto 3} & 12 & 3 \\
\hline
\mbox{Objeto 4} & 14 & 4 \\
\hline
\end{array}
\] 
entonces la función anterior generaría la siguiente tabla
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c}
\multicolumn{1}{c}{} & \multicolumn{11}{c}{\mbox{peso disponible en la mochila}}
& \\
\cline{2-12}
\multicolumn{1}{c|}{\mbox{nº objetos}} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9
& 10\\ \cline{1-12}
0 &0 &0 &0 &0 &0 &20 &20 &20 &20 &20 &20 &\\ \cline{1-12}
1 &0 &0 &0 &0 &15 &20 &20 &20 &20 &35 &35 &\\ \cline{1-12}
2 &0 &0 &10 &10 &15 &20 &25 &30 &30 &35 &35 &\\ \cline{1-12}
3 &0 &0 &10 &12 &15 &22 &25 &30 &32 &37 &42\\ \cline{1-12}
4 &0 &0 &10 &12 &15 &22 &25 &30 &32 &37 & \alert{\textbf{42}} & \leftarrow
\mbox{SOLUCIÓN}
\\
\cline{1-12}
\end{array}
\]
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema de la mochila entera}
\framesubtitle{Ejemplo con programación dinámica}
La función anterior nos da el valor máximo de la mochila pero no nos da los
objetos que entrarían en ella. Para ello podemos utilizar la tabla
recorriendola al revés.

La siguiente función nos devuelve los objetos introducidos a partir de la tabla
dinámica:
\begin{lstlisting}
void objetos(int n, int v[n], int p[n], int pmax,
             int f[n][pmax], int sol[n]){
  for (int i=n-1; i>0; i--)
    if (p[i] > pmax) sol[i] = 0;
    else 
      if (f[i-1][pmax-p[i]]+v[i] > f[i-1][pmax]){
        sol[i] = 1;
        pmax -= p[i]; 
      } 
      else sol[i] = 0; 
  if (p[0] < pmax) sol[0] = 1; 
  else sol[0] = 0;
  return;
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema de la mochila entera}
\framesubtitle{Coste temporal}
\begin{itemize}
\item Cada componente de la tabla se calcula en un tiempo constante, luego la
construcción de la tabla es $O(np_{max})$. 
\item Por otro lado, la función que determina los objetos introducidos en la
mochila a partir de la tabla, sólo tiene un bucle que recorre todos los objetos
para ver si están o no dentro de la mochila. Como el cuerpo del bucle tiene un
coste constante, su coste es $O(n)$. 
\item Así pues, el coste total es $O(np_{max}) + O(n)= O(npmax)$.
\item Se observa que si pmax es muy grande ($p_{max}\geq n$) sería un coste
cuadrático o superior, por lo que no sería muy eficiente. 
\end{itemize} 
\end{frame}


\subsubsection{El problema del viajante}
%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
Un viajante tiene que recorrer $n$ ciudades y regresar a la ciudad de partida,
sin pasar dos veces por la misma ciudad. 

Se supone que los caminos son
unidireccionales y se conoce la distancia de cada camino. 

\emph{¿Cuál es recorrido que debe seguir para que sea lo más corto posible?}
\[
\psmatrix[colsep=1.5cm,rowsep=1cm,nodesep=3pt]
& \textcolor{red}{3}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}  \\
\textcolor{red}{2}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}} & & \raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}\textcolor{red}{0}\\
& \textcolor{red}{1}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}
\ncline{->}{2,1}{2,3}^{\qquad 2}
\ncline{->}{1,2}{2,1}<{4}
\ncline{->}{1,2}{2,3}>{2}
\ncline{->}{1,2}{3,2}<{\raisebox{1cm}{5}}
\ncline{->}{2,3}{3,2}>{3}
\ncline{->}{3,2}{2,1}<{4}
\ncarc[arcangle=30]{->}{2,1}{1,2}<{6}
\ncarc[arcangle=-30]{->}{2,3}{1,2}>{3}
\ncarc[arcangle=-30]{->}{2,1}{3,2}<{6}
\ncarc[arcangle=-30]{->}{3,2}{2,3}>{5}
\endpsmatrix
\qquad
\raisebox{1cm}{\includegraphics[scale=0.5]{img/viajante}}
\]
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Modelización mediante grafos}
Si representamos cada ciudad mediante un nodo de un grafo y cada camino como
una arista dirigida, tendremos un grafo dirigido $G=(V,A)$ donde:
\begin{itemize}
  \item $V={1,…,n}$ es el conjunto de vértices (ciudades).
  \item $A$ es el conjunto de aristas $(i,j)$ con $i,j \in V$ (caminos).
  \item $D(i,j)$ es la longitud de $(i,j)$ si $(i,j)\in A$, o $\infty$ si
  $(i,j)\not\in A$.
\end{itemize}
\[
\scalebox{0.7}{
\psmatrix[colsep=1.5cm,rowsep=1cm,nodesep=3pt]
& \textcolor{red}{3}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}  \\
\textcolor{red}{2}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}} & & \raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}\textcolor{red}{0}\\
& \textcolor{red}{1}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}
\ncline{->}{2,1}{2,3}^{\qquad 2}
\ncline{->}{1,2}{2,1}<{4}
\ncline{->}{1,2}{2,3}>{2}
\ncline{->}{1,2}{3,2}<{\raisebox{1cm}{5}}
\ncline{->}{2,3}{3,2}>{3}
\ncline{->}{3,2}{2,1}<{4}
\ncarc[arcangle=30]{->}{2,1}{1,2}<{6}
\ncarc[arcangle=-30]{->}{2,3}{1,2}>{3}
\ncarc[arcangle=-30]{->}{2,1}{3,2}<{6}
\ncarc[arcangle=-30]{->}{3,2}{2,3}>{5}
\endpsmatrix
}
\quad
\begin{array}[b]{|c|c|c|c|c|}
\hline
\mbox{De}\backslash\mbox{A} & 0 & 1 & 2 & 3 \\
\hline 
0 & \infty & 3 & \infty & 3 \\
\hline 
1 & 5 & \infty & 4 & \infty \\
\hline 
2 & 2 & 6 & \infty & 6 \\
\hline 
3 & 2 & 5 & 4 & \infty\\
\hline
\end{array}
\]
Se trata de un problema de búsqueda en un grafo del ciclo Hamiltoniano de longitud mínima.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Función de recurrencia}
Suponiendo que la ciudad de partida es la $0$, si llamamos $C(i,W)$ a la
longitud del camino mínimo desde el vértice $i$ hasta el $0$ que pasa por todos
los vértices de $W \subset V$, siendo $0\not\in W$, entonces la solución al
problema vendrá dada por $C(0,W\setminus\{0\})$.

Teniendo en cuenta el principio de optimalidad, podemos definir $C(i,W)$ de
manera recursiva mediante la siguiente ecuación:
\[
C(i,W)=
\begin{cases}
D(i,0) & \mbox{si $W=\emptyset$,}\\
\min_{j\in W}\{D(i,j)+C(j,W\setminus\{j\})\} & \mbox{si $W\neq \emptyset$.}
\end{cases}
\]
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema del viajante}
\framesubtitle{Implementación en Java (versión recursiva)}
\begin{lstlisting}
/* viajante.java
 * i es la ciudad actual.
 * W es el conjunto de ciudades por las que aun no se ha pasado.
 * Devuelve la distancia del recorrido menor.
 */
private double C(int i, Conjunto w) {
  Conjunto w1 = new Conjunto(w);
  w1.eliminar(i);
  if (w1.vacio()) return this.dist(i, 0);
  double dist, dmin=Double.MAX_VALUE;
  for (int j = 0; j < this.numCiudades(); j++)
    if (w1.pertenece(j)) {
      dist = this.dist(i, j) + C(j,w1);
      if (dist<dmin) dmin = dist;
    }
  return dmin;
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema del viajante}
\framesubtitle{Implementación recursiva}
Donde la clase \texttt{Conjunto} tiene la siguiente interfaz:
\begin{lstlisting}
// conjunto.java
public class Conjunto {
  private boolean[] elementos;
  public Conjunto(int n) {} // Constructor por defecto
  public Conjunto(Conjunto v) {} // Constructor de copia
  public void incluir(int i) {} // Incluye el elemento i 
  public void eliminar(int i) {} // Elimina el elemento i
  public boolean pertenece(int i) {} // Pertenencia de i
  public boolean empty() {} // Comprueba si esta vacio
  public int id() {}  // Identificador del conjunto
  public void print() {} // Imprime el conjunto
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Recorrido del espacio de búsqueda}
Esta función estudia todos los posibles caminos por fuerza bruta.
\begin{center}
\newcommand{\Tlabel}[1]{\tlput{\footnotesize #1}}
\pstree[thislinestyle=none,thislevelsep=0]{}{
\pstree[nodesep=2pt,levelsep=1cm,arrows=->,treenodesize=0.5cm]{\TR{0}}{ 
	\pstree{\TR{1}\Tlabel{3}}{
       \pstree{\TR{2}\Tlabel{4}}{
       		\pstree{\TR{3}\Tlabel{6}}{
       			\pstree[linestyle=none,arrows=none]{\TR{0}\Tlabel{2}}{\TR{15}\tvput{\rule{1cm}{0.2pt}}} 
       		}
       	}
       \pstree{\TR{3}\Tlabel{$\infty$}}{
       		\pstree{\TR{2}\Tlabel{4}}{
       			\pstree[linestyle=none,arrows=none]{\TR{0}\Tlabel{2}}{\TR{$\infty$}\tvput{\rule{1cm}{0.2pt}}}
       		}
       	}
	}
	\pstree{\TR{2}\Tlabel{$\infty$}}{
       \pstree{\TR{1}\Tlabel{6}}{
       		\pstree{\TR{3}\Tlabel{$\infty$}}{
       			\pstree[linestyle=none,arrows=none]{\TR{0}\Tlabel{2}}{\TR{$\infty$}\tvput{\rule{1cm}{0.2pt}}}
       		}
       	}
       	\pstree{\TR{3}\Tlabel{6}}{
       		\pstree{\TR{1}\Tlabel{5}}{
       			\pstree[linestyle=none,arrows=none]{\TR{0}\Tlabel{5}}{\TR{$\infty$}\tvput{\rule{1cm}{0.2pt}}} 
       		} 
       	}
	} 	
    \pstree{\TR{3}\Tlabel{3}}{ 
    	\pstree{\TR{1}\Tlabel{5}}{ 
    		\pstree{\TR{2}\Tlabel{4}}{ 
    			\pstree[linestyle=none,arrows=none]{\TR{0}\Tlabel{2}}{\TR{\fbox{\color{red}14}}\tvput{\rule{1cm}{0.2pt}}} } 
    		} 
    	\pstree{\TR{2}\Tlabel{4}}{ 
    		\pstree{\TR{1}\Tlabel{6}}{
       			\pstree[linestyle=none,arrows=none]{\TR{0}\Tlabel{5}}{\TR{18}\tvput{\rule{1cm}{0.2pt}}}
       		}
       	}
	}
}
\pstree[linestyle=none,nodesep=2pt,levelsep=1cm]{\TR{Origen}}{
	\pstree{\TR{1ª visita}}{
		\pstree{\TR{2ª visita}}{
			\pstree{\TR{3ª visita}}{
			 	\pstree{\TR{Destino}}{\TR{Distancia}}
			 }
		}
	}
}
}
\end{center}
\centerline{\alert{\emph{¡El coste de este algoritmo es $O(n!)$!}}}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Mejora por programación dinámica}
La función anterior repite llamadas para calcular $C(i,W)$, y por tanto es ineficiente. 

Utilizando la técnica de programación dinámica, podemos guardar los valores de $C(i,W)$ en una tabla para evitar repetir su cálculo.

Para indexar la tabla en la segunda dimensión, asignaremos un código único a cada subconjunto $W$ para identificarlo.
Puesto que el número de ciudades es $n$, el número de posibles subconjuntos es $2^n$. Si representamos cada subconjunto mediante un vector
\[
W(x_0,x_1,\lots,x_{n-1}) \mbox{ con } x_i= 
\begin{cases}
1 & \mbox{si $i\in W$,}\\
0 & \mbox{si $i\not\in W$.}
\end{cases}
\]
entonces, la función
\[
id(W) = x_02^0 + x_12^1 +\ldots+ x_{n-1}2^{n-1}
\]
asigna un entero único a cada subconjunto.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema del viajante}
\framesubtitle{Implementación con programación dinámica}
\begin{lstlisting}
/* viajante_dinamica.java
 * i es el numero de ciudad de partida.
 * w es el conjunto de ciudades por las que aun no se ha pasado.
 * c es la tabla dinamica.
 */
private double C(int i, Conjunto w, double[][] c) {
  Conjunto w1 = new Conjunto(w);
  w1.eliminar(i);
  if (w1.vacio()) return this.dist(i, 0);
  if (c[i][w1.id()]>0) return c[i][w1.id()];
  double dist, dmin = Double.MAX_VALUE;
  for (int j = 0; j < this.numCiudades(); j++)
    if (w1.pertenece(j)) {
      dist = this.dist(i, j) + C(j,w1);
      if (dist<dmin) dmin = dist;
    }
  c[i][w1.id()] = dmin;
  return dmin;
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Ejemplo con programación dinámica}
Para el ejemplo anterior con $D(i,j)$
\[
\begin{array}[b]{|c|c|c|c|c|}
\hline
\mbox{De}\backslash\mbox{A} & 0 & 1 & 2 & 3 \\
\hline 
0 & \infty & 3 & \infty & 3 \\
\hline 
1 & 5 & \infty & 4 & \infty \\
\hline 
2 & 2 & 6 & \infty & 6 \\
\hline 
3 & 2 & 5 & 4 & \infty\\
\hline
\end{array}
\] 
la tabla de distancias mínimas resultante $C(i,W)$ es
\[
\scriptsize
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
i\backslash W & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\\ \hline 
0 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & \alert{\textbf{14}} & -1\\ \hline
1 & -1 & -1 & -1 & -1 & 6 & -1 & -1 & -1 & \infty & -1 & -1 & -1 & 12 & -1 & -1 & -1\\ \hline
2 & -1 & -1 & 11 & -1 & -1 & -1 & -1 & -1 & 8 & -1 & 16 & -1 & -1 & -1 & -1 & -1\\ \hline
3 & -1 & -1 & 10 & -1 & 6 & -1 & 11 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1\\ \hline
\end{array}
\]
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Coste de la programación dinámica}
El coste del algoritmo para completar la tabla $C(i,W)$ supone:
\begin{itemize}
\item Cálculo de $C(i,\emptyset)$ para $i=1,\ldots,n-1$: $n-1$ consultas a tabla;
\item Cálculo de $C(i,W)$ para $i\leq k = \mbox{Cardinal}(W) \leq n-2$:
\[
(n-1)\binom{n-2}{k}k \mbox{ sumas};
\]
\item Cálculo de $C(0,V)$: $n-1$ sumas.
\end{itemize}
En total
\[
\Theta\left((2(n-1)+\sum_{k=1}^{n-2}(n-1)k\binom{n-2}{k}\right) = \Theta(n^22^n),
\]
que aunque es exponencial, es de menor orden que $O(n!)$.

El precio de esta mejora es el coste espacial de la tabla $C(i,W)$ que es $\Theta(n2^n)$.
\end{frame} 


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema del viajante}
\framesubtitle{Itinerario del recorrido mínimo}
El itinerario del recorrido mínimo podemos calcularlo a partir de la tabla $C(i,W)$ mediante la siguiente función
\begin{lstlisting}
// viajante_dinamica.java
public void camino_min(int n, Conjunto w, double[][] c, 
                       int[] camino) {
  double dist, dmin; int jmin;
  for (int i=1; i<n; i++){
    dmin = Double.MAX_VALUE;
    for (int j=0; j<n; j++)
      if (w.pertenece(j)){
        w.eliminar(j);
        dist = d[camino[i-1]][j]+c[j][w.id()]];
        w.incluir(j);
        if (dist<dmin) { dmin = dist; jmin = j;}
      }
    camino[i] = jmin; 
    w.eliminar(jmin);
  }
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Itinerario del recorrido mínimo}
Para el ejemplo, la función anterior devuelve el itinerario \texttt{camino[4]=\{0,3,1,2\}}, es decir
\[
\psmatrix[colsep=1.5cm,rowsep=1cm,nodesep=3pt]
& \textcolor{red}{3}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}  \\
\textcolor{red}{2}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}} & & \raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}\textcolor{red}{0}\\
& \textcolor{red}{1}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}
\ncline[linecolor=green]{->}{2,1}{2,3}^{\qquad \textcolor{green}{2}}
\ncline{->}{1,2}{2,1}<{4}
\ncline{->}{1,2}{2,3}>{2}
\ncline[linecolor=green]{->}{1,2}{3,2}<{\raisebox{1cm}{\textcolor{green}{5}}}
\ncline{->}{2,3}{3,2}>{3}
\ncline[linecolor=green]{->}{3,2}{2,1}<{\textcolor{green}{4}}
\ncarc[arcangle=30]{->}{2,1}{1,2}<{6}
\ncarc[linecolor=green,arcangle=-30]{->}{2,3}{1,2}>{\textcolor{green}{3}}
\ncarc[arcangle=-30]{->}{2,1}{3,2}<{6}
\ncarc[arcangle=-30]{->}{3,2}{2,3}>{5}
\endpsmatrix
\]
\begin{center}
\emph{¡Que efectivamente es el camino de mínima longitud!}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Camínos mínimos en un grafo}
\framesubtitle{Ejemplo con programación dinámica}

Sea $G=\langel V,A\rangle$ un grafo dirigido con pesos en sus aristas.
Queremos calcular el \hyperlink{caminos_minimos<1>}{camino mínimo} entre dos
vértices cualesquiera del grafo.

\begin{center}
\scalebox{0.75}{
\begin{pspicture}(0,0)(6,4.5)
{\psset{fillstyle=solid,fillcolor=orange}
\cnodeput(0,4){A}{$A$}
\cnodeput(2,4){B}{$B$}
\cnodeput(6,4){C}{$C$}
\cnodeput(0,2){D}{$D$}
\cnodeput(4,2){E}{$E$}
\cnodeput(2,0){F}{$F$}
\cnodeput(6,0){G}{$G$}
}
\newcommand\arc[4][black]{%
    \ncline[linecolor=#1]{->}{#2}{#3}
    \ncput{\colorbox{white}{#4}}
}
\arc{A}{B}{3}
\arc{B}{E}{7}
\arc{C}{B}{8}
\arc{D}{A}{5}
\arc{D}{B}{9}
\arc[green]{D}{F}{6}
\arc[green]{E}{C}{5}
\arc{E}{D}{15}
\arc{E}{G}{9}
\arc[green]{F}{E}{8}
\arc{F}{G}{11}
\arc{G}{C}{3}
\end{pspicture}
}

Camino mínimo del vértice $D$ al vértice $C$. Su peso es 19.
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Búsqueda de caminos mínimos: Algoritmo de Floyd}
\framesubtitle{Función de recurrencia}
A diferencia del algoritmo de Dijkstra, ahora no vamos a calcular el camino
mínimo entre un vértice y todos los demás del grafo, sino entre dos vértices
cualesquiera $i$ y $j$. 

Si llamamos $C(i,j,k)$ a la función que devuelve la distancia del
camino mínimo que va del vértice $i$ al vértice $j$ pudiendo pasar por los $k$
primeros vértices del grafo. Está claro que la solución al problema será
$C(i,j,n)$ donde $n$ es el número total de vértices del grafo.

Si llamamos $d_{ij}$ a la distancia de la arista que une el vértice $i$ con el
$j$, podemos definir esta función de recurrencia mediante la siguiente ecuación:
\[
C(i,j,k)=
\begin{cases}
d_{ij} & \mbox{si $k=0$,}\\
\min\{C(i,j,k-1),C(i,k,k-1)+C(k,j,k-1)\} & \mbox{si $k>0$.}
\end{cases}
\]
\end{frame}




%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Búsqueda de caminos mínimos: Algoritmo de Floyd}
\framesubtitle{Tabla dinámica}
Para guardar los valores de la función $C(i,j,k)$
necesitamos una tabla tridimensional, pues la función depende de tres
parámetros. 

Sin embargo, es posible recucir el coste espacial y utilizar una tabla
bidimensional que se vaya reescribiendo para cada valor de $k$. En esta tabla,
las filas representarían el vértice de partida $i$ y las columnas el vértice de
llegada $j$.

Para no sobreescribir valores que posteriormente se necesiten, es preciso
observar la celdas que se necesitan para calcular cualquier celda.

\begin{center}
\scalebox{0.5}{
\begin{pspicture}(0,0)(12,5)
\rput[b](3,1){
\[
\renewcommand{\arraystretch}{2}
\begin{array}{c|c|c|c|c|c|}
\multicolumn{2}{c}{} & \multicolumn{1}{c}{k} & \multicolumn{1}{c}{} &
\multicolumn{1}{c}{j} & \multicolumn{1}{c}{} \\
\cline{2-6} 
 & \cdtos & & \cdtos & &\cdots \\
 \cline{2-6}
 k & \cdots & & \cdots & \cellcolor{orange}C(k,j) & \cdots\\
 \cline{2-6}
 & \cdtos & & \cdtos & &\cdots \\
 \cline{2-6}
 i & \cdots & \cellcolor{orange}C(i,k) & \cdots & \cellcolor{orange}C(i,j) &
 \cdots\\
 \cline{2-6}
 & \cdtos & & \cdtos & &\cdots \\
 \cline{2-6}
\end{array}
\]
}

\rput[b](9,1){
\[
\renewcommand{\arraystretch}{2}
\begin{array}{c|c|c|c|c|c|}
\multicolumn{2}{c}{} & \multicolumn{1}{c}{k} & \multicolumn{1}{c}{} &
\multicolumn{1}{c}{j} & \multicolumn{1}{c}{} \\
\cline{2-6} 
 & \cdtos & & \cdtos & &\cdots \\
 \cline{2-6}
 k & \cdots & & \cdots & & \cdots\\
 \cline{2-6}
 & \cdtos & & \cdtos & &\cdots \\
 \cline{2-6}
 i & \cdots & & \cdots & \cellcolor{green}C(i,j) & \cdots\\
 \cline{2-6}
 & \cdtos & & \cdtos & &\cdots \\
 \cline{2-6}
\end{array}
\]
}
\rput[b](3,0){Etapa $k-1$}
\rput[b](9,0){Etapa $k$}
\psset{linewidth=1.5pt}
\psline{->}(5,2.2)(9.5,2.2)
\psline{->}(5,3.8)(9.5,2.3)
\pscurve{->}(2.8,2.1)(5,1.2)(9.5,2.1)
\end{pspicture}
}
\end{center}
Como las celdas de la fila $k$ y columna $k$ no cambian de la etapa $k-1$ a la
etapa $k$, puesto que corresponden a caminos que empiezan o terminan en el
vértice $k$, no hay problemas al reescribir la tabla.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Búsqueda de caminos mínimos: Algoritmo de Floyd} 
\framesubtitle{Implementación en Java (versión iterativa con ahorro
de memoria)}
\begin{lstlisting}
/* floyd.java
 * g es un grafo dirigido con etiquetado.
 * i es el vertice origen.
 * j es el vertice destino.
 */
public int[] Floyd(Graph g, int inicio, int fin) {
  int n = g.numVertices(); // Numero de vertices del grafo
  int t[] = new int[n][n][x+1];  // Tabla dinamica
  // Rellenamos los casos base
  for (int i=0; i<g.numVertices(); i++)
    for (int j=0; i<g.numVertices(); j++) {
      t[i][j] = g.peso(i,j);
      camino[i][j] = 0;  // Indica que el camino es directo
    }
  // Reescribimos la tabla para cada valor de k.
  for (int k=0; k<g.numVertices(); k++)
    for (int i=0; i<g.numVertices(); i++)
      for (int j=0; j<g.numVertices(); j++)
        if (t[i][k] + t[k][j] < t[i][j]){
          t[i][j] = t[i][k] + t[k][j];
          camino[i][j] = k;  // El camino pasa por k
        }  
  return t[i][j]; 
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Construcción del itinerario del camíno mínimo} 
\framesubtitle{Implementación en Java}
A partir de la tabla \texttt{camino} construida con el algoritmo de Flyd, es
posible construir el itinerario del camino mínimo de manera recursiva.
\begin{lstlisting}
/* floyd.java
 * i es el vertice origen.
 * j es el vertice destino.
 * camino[][] es la tabla construida con el algoritmo de Floyd.
 * Si camino[i][j]=k quiere decir que el camino minimo de i a j pasa por k.
 */
public void itinerario (int i, int j, int camino[][]){
  if (itinerario[i][j]==0) cout << ", " << j;
  else{
    itinerario(i, camino[i][j], camino);
    itinerario(camino[i][j], j, camino);
  }    
  return; 
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Búsqueda del camíno mínimo: Algoritmo de Floyd} 
\framesubtitle{Aplicación a distancias en mapas}
Una aplicación interesante del algoritmo de Floyd es para calcular las
distancias mínimas entre los puntos de un mapa. 
\[
\includegraphics[scale=0.4]{img/mapa1} 
\]
Los vértices del grafo serían los puntos o ciudades y las aristas las
comunicaciones por carretera u otro tipo de vía.
\end{frame}



%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Búsqueda del camíno mínimo: Algoritmo de Floyd} 
\framesubtitle{Aplicación a distancias en mapas}
Por ejemplo, dado un conjunto de ciudades a las que hay que viajar podríamos
calcular las distancias mínimas de cada una de ellas a las demás para ver dónde
interesa ubicar un centro logístico.
\[
\includegraphics[scale=0.36]{img/mapa2} 
\]
\end{frame}
